import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: LCR 078. 合并 K 个升序链表
 * <a href="https://leetcode.cn/problems/vvXgSW/description/">...</a>
 * User: DELL
 * Date: 2023-10-16
 * Time: 17:36
 */


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    /**
     * 解题思路: (堆)
     * 本题主要是维护一个小根堆,同时传入自定义的比较器即可,较为简单.
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 非空校验
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode newHead = new ListNode();
        // 辅助堆,同时自定义比较器
        PriorityQueue<ListNode> heap = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
        // 先将每个链表的第一个非 null 节点入堆
        int len = lists.length;
        for (int i = 0; i < len; i++) {
            if (lists[i] != null) {
                heap.offer(lists[i]);
            }
        }
        // 依次去除 val 最小的节点
        ListNode cur = newHead;
        while (!heap.isEmpty()) {
            ListNode temp = heap.poll();
            cur.next = temp;
            cur = temp;
            if (temp.next != null) {
                heap.offer(temp.next);
            }
        }
        return newHead.next;
    }
}